package com.sunny;

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<Integer> pre = Arrays.asList(1,2,4,5,8,3,6,9,7);
        List<Integer> in = Arrays.asList(4,2,8,5,1,9,6,3,7);

        Node root = getTree(pre, 0, in, 0, 8);

        postOrder(root);
    }

    public static void postOrder(Node node){
        if(null != node.getLeft())
            postOrder(node.getLeft());
        if(null != node.getRight())
            postOrder(node.getRight());
        System.out.print(node.getValue());
    }

    public static Node getTree(List<Integer> pre,int ind, List<Integer> in, int s, int t){

        if(s>t)
            return null;

        if(s == t)
            return new Node(in.get(s));

        Node node = new Node(pre.get(ind));
        int mid = getMid(in, s, t, node.getValue());

        node.setLeft(getTree(pre, ind+1, in, s, mid-1));
        node.setRight(getTree(pre, ind+mid-s+1, in, mid+1,t));

        return node;
    }

    public static int getMid(List<Integer> in, int s, int t, int val){

        int res = 0;
        for(int i=0;i<in.size();i++){
            if(val == in.get(i)) {
                res = i;
                break;
            }
        }
        return res;
    }

}

class Node{

    int value;
    Node left,right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}